This invention relates to cryptography and more particularly, to format-preserving cryptography.
Cryptographic systems are used to secure data in a variety of contexts. For example, encryption algorithms are used to encrypt sensitive information such as financial account numbers, social security numbers, and other personal information. By encrypting sensitive data prior to transmission over a communications network, the sensitive data is secured, even if it passes over an unsecured communications channel. Sensitive data is also sometimes encrypted prior to storage in a database. This helps to prevent unauthorized access to the sensitive data by an intruder.
Commonly used encryption algorithms include the Advanced Encryption Standard (AES) encryption algorithm and the Data Encryption Standard (DES) encryption algorithm. Using these types of algorithms, an organization that desires to secure a large quantity of sensitive information can place the sensitive information in a data file. The data file can then be encrypted in its entirety using the AES or DES algorithms.
Encrypting entire files of data can be an effective technique for securing large quantities of data. However, bulk encryption of files can be inefficient and cumbersome because it is not possible to selectively access a portion of the encrypted data in an encrypted file. Even if an application only needs to have access to a portion of the data, the entire file must be decrypted. Without the ability to selectively decrypt part of a file, it can be difficult to design a data processing system that provides different levels of data access for different application programs and for different personnel.
To avoid the difficulties associated with encrypting entire files of sensitive data, it would be desirable to be able to apply cryptographic techniques such as the AES and DES encryption algorithms with a finer degree of granularity. For example, it might be desirable to individually encrypt social security numbers in a database table, rather than encrypting the entire table. This would allow software applications that need to access information in the table that is not sensitive to retrieve the desired information without decrypting the entire table.
Conventional encryption techniques can, however, significantly alter the format of a data item. For example, encryption of a numeric string such as a credit card number may produce a string that contains non-numeric characters or a string with a different number of characters. Because the format of the string is altered by the encryption process, it may not be possible to store the encrypted string in the same type of database table that is used to store unencrypted versions of the string. The altered format of the encrypted string may therefore disrupt software applications that need to access the string from a database. The altered format may also create problems when passing the encrypted string between applications. Because of these compatibility problems, organizations may be unable to incorporate cryptographic capabilities into legacy data processing systems.
To address the problems associated with altering the format of a string during cryptographic operations, so-called format-preserving encryption (FPE) algorithms have been proposed. When an FPE algorithm is used to encrypt or decrypt a string in a given format, the format of the string is not changed during the encryption or decryption process. Although FPE algorithms can be helpful in avoiding the disruptions associated with altered string formats, the characteristics of strings that have been cryptographically processed using FPE algorithms may be changed sufficiently to give rise to incompatibilities with software applications. FPE algorithms are able to ensure that an encrypted or decrypted string will contain only valid characters, but may not maintain desired relationships between those characters. For example, the checksum value that is associated with a credit card number may no longer be valid after the credit card number has been encrypted using an FPE algorithm. As another example, a string whose digits are required to be monotonically ascending may no longer satisfy this requirement following encryption or decryption using an FPE algorithm. In other situations, it can be challenging to properly handle data in a database where it is not clear which data items have been encrypted using an FPE algorithm and which items have remained unencrypted.
It would therefore be desirable to provide improved ways in which to cryptographically process data in a system involving format preserving encryption (FPE) algorithms.